{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个只包括 <code>'('</code>，<code>')'</code>，<code>'{'</code>，<code>'}'</code>，<code>'['</code>，<code>']'</code>&nbsp;的字符串 <code>s</code> ，判断字符串是否有效。</p>\n",
    "\n",
    "<p>有效字符串需满足：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>左括号必须用相同类型的右括号闭合。</li>\n",
    "\t<li>左括号必须以正确的顺序闭合。</li>\n",
    "\t<li>每个右括号都有一个对应的相同类型的左括号。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"()\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"()[]{}\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(]\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 仅由括号 <code>'()[]{}'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-parentheses](https://leetcode.cn/problems/valid-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-parentheses](https://leetcode.cn/problems/valid-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"()\"', '\"()[]{}\"', '\"(]\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        for i in range(len(s), -1, -1):\n",
    "            prev = 0\n",
    "            for j in range(i+1, n):\n",
    "                nprev = dp[j]\n",
    "                if s[i]==s[j]:\n",
    "                    dp[j] = prev\n",
    "                else:\n",
    "                    dp[j]=1+min(dp[j], dp[j-1])\n",
    "                prev = nprev\n",
    "        return dp[-1]<=k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [0 for _end in range(len(s))] \n",
    "\n",
    "        for start in range(len(s) - 1, -1, -1):\n",
    "            prev = 0\n",
    "            for end in range(start + 1, len(s)):\n",
    "                temp = validStat[end]\n",
    "\n",
    "                if s[start] == s[end]:\n",
    "                    validStat[end] = prev\n",
    "                else:\n",
    "                    validStat[end] = min(validStat[end], validStat[end - 1]) + 1\n",
    "                prev = temp\n",
    "        minK = validStat[len(s) - 1]\n",
    "        return minK <= k\n",
    "\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是k回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1):\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1])\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是k回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1):\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1])\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     # 区间i,j 能否在k宽容度下成为palindrome\n",
    "        #     if j-i+1 <= k:\n",
    "        #         return True\n",
    "        #     elif k == -1:\n",
    "        #         return False\n",
    "            \n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1,k)\n",
    "            \n",
    "        #     return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        # return dfs(0,n-1,k)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     # to make ij palindrome, minimal k\n",
    "        #     if i >= j:\n",
    "        #         return 0\n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1)\n",
    "        #     return min(dfs(i+1,j), dfs(i,j-1))+1\n",
    "        # return dfs(0,n-1) <= k\n",
    "\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j-1, -1, -1):\n",
    "                # [i,j]\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1]\n",
    "                else:\n",
    "                    f[i][j] = min(f[i+1][j], f[i][j-1])+1\n",
    "        return f[0][n-1] <= k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        if len(s) <= k:\n",
    "            return True\n",
    "\n",
    "        # dp[i][j]: longest palindrome length within [i, j]\n",
    "        dp = [[0] * len(s) for _ in range(len(s))]\n",
    "\n",
    "        for j in range(0, len(s)):\n",
    "            dp[j][j] = 1\n",
    "            for i in reversed(range(j)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        return len(s) - dp[0][-1] <= k\n",
    "\n",
    "\n",
    "#  a (a) b a a b (a) b b a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[0 for j in range(n)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])\n",
    "        return len(s) - dp[0][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n=len(s)\n",
    "        dp=[[0 for _ in range(n)] for _ in range(n)]\n",
    "        if 1+k>=n:\n",
    "            return True\n",
    "        for l in range(n-2,-1,-1):\n",
    "            dp[l][l]=1\n",
    "            for r in range(l+1,n):\n",
    "                if s[l]==s[r]:\n",
    "                    dp[l][r]=dp[l+1][r-1]+2\n",
    "                else:\n",
    "                    dp[l][r]=max(dp[l+1][r],dp[l][r-1])\n",
    "                if dp[l][r]+k>=n:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [[0 for _end in range(len(s))] for _start in range(len(s))]\n",
    "        for start in range(len(s) - 1, -1, -1):\n",
    "            for end in range(start + 1, len(s)):\n",
    "                if s[start] == s[end]:\n",
    "                    validStat[start][end] = validStat[start + 1][end - 1]\n",
    "                else:\n",
    "                    validStat[start][end] = min(validStat[start + 1][end], validStat[start][end - 1]) + 1\n",
    "        \n",
    "        minK = validStat[0][len(s) - 1]\n",
    "        return minK <= k\n",
    "\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是x回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1) # 删掉1个数（2种位置），k+1\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1]) # 端点相同，可以不删，也可以删（取k最小）\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        #最长回文子序列.\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]  #每个字母自己。都是一个长度为1的回文串\n",
    "\n",
    "        if 1 + k >= n:\n",
    "            return True\n",
    "\n",
    "        for l in range(n-2, -1, -1):    #l依赖于l+1\n",
    "            dp[l][l] = 1            \n",
    "            for r in range(l + 1, n):   #r依赖于r-1\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l+1][r-1] + 2\n",
    "                else:\n",
    "                    dp[l][r] = max(dp[l+1][r], dp[l][r-1])\n",
    "                \n",
    "                if dp[l][r] + k >= n:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [ [0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n, 1):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])\n",
    "        return dp[0][n-1] + k >= len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        t = s[::-1]\n",
    "        l = len(s)\n",
    "\n",
    "        dp = [[0] * (l + 1) for _ in range(l + 1)]\n",
    "\n",
    "        for i in range(1, l + 1):\n",
    "            for j in range(1, l + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        \n",
    "        return (l - dp[l][l]) <= k\n",
    "\n",
    "\n",
    "    # def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "    #     l = len(s)\n",
    "    #     dp = [[[True if i == j else False] * (k + 1) for j in range(l + 1)] for i in range(l + 1)]\n",
    "\n",
    "    #     def isPalindrome(word):\n",
    "    #         l = len(word) // 2\n",
    "    #         for i in range(l):\n",
    "    #             if word[i] != word[len(word) - 1 - i]:\n",
    "    #                 return False\n",
    "    #         return True\n",
    "\n",
    "    #     for i in range(l, 0, -1):\n",
    "    #         for j in range(i, l + 1):\n",
    "    #             for t in range(k + 1):\n",
    "    #                 max_len = j - i + 1\n",
    "    #                 if t > max_len:\n",
    "    #                     dp[i][j][t] = True\n",
    "    #                     continue\n",
    "    #                 if t == 0:\n",
    "    #                     word = s[i - 1:j + 1 - 1]\n",
    "    #                     dp[i][j][t] = isPalindrome(word)\n",
    "    #                 else:\n",
    "    #                     if i == j:\n",
    "    #                         continue\n",
    "    #                     if s[i - 1] == s[j - 1]:\n",
    "    #                         dp[i][j][t] = dp[i + 1][j - 1][t]\n",
    "    #                     else:\n",
    "    #                         dp[i][j][t] = dp[i][j - 1][t - 1] or dp[i + 1][j][t - 1]\n",
    "    #     return dp[1][l][k]\n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if j - i < 1:\n",
    "                    f[i][j] = 0\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        f[i][j] = f[i + 1][j - 1]\n",
    "                    else:\n",
    "                        f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1\n",
    "        return f[0][n - 1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        #最长回文子序列.\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]  #每个字母自己。都是一个长度为1的回文串\n",
    "\n",
    "        if 1 + k >= n:\n",
    "            return True\n",
    "\n",
    "        for l in range(n-2, -1, -1):    #l依赖于l+1\n",
    "            dp[l][l] = 1            \n",
    "            for r in range(l + 1, n):   #r依赖于r-1\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l+1][r-1] + 2\n",
    "                else:\n",
    "                    dp[l][r] = max(dp[l+1][r], dp[l][r-1])\n",
    "                \n",
    "                if dp[l][r] + k >= n:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = i+l-1\n",
    "                if j >= n: break\n",
    "                if s[i] == s[j]:\n",
    "                    if l == 2:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    if l == 2:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "        return dp[0][-1] <= k\n",
    "\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def isValid(left, right, k):\n",
    "        #     while left < right:\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #             right -= 1\n",
    "        #         else:\n",
    "        #             if k > 0:\n",
    "        #                 k -= 1\n",
    "        #                 return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "        #             else:\n",
    "        #                 return False\n",
    "        #     return True \n",
    "        # return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "\n",
    "        return dp[0][-1] + k >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        re_s = \"\".join(list(s)[::-1] )\n",
    "        lens = len(s)\n",
    "        dp = [[0 for _ in range(lens+1)]for _ in range(lens+1)]\n",
    "\n",
    "        for i in range(1, lens+1):\n",
    "            for j in range(1, lens+1):\n",
    "                if s[i-1] == re_s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return lens-dp[-1][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        reversed_s = s[::-1]\n",
    "        n = len(s)\n",
    "        \n",
    "        # Initialize a dp array\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        \n",
    "        # Fill the dp array\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if s[i-1] == reversed_s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        # If the length of s minus the value in the bottom-right corner of the dp array (i.e., the length of LCS) \n",
    "        # is less than or equal to k, then it's a valid palindrome.\n",
    "        return n - dp[n][n] <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        t = s[::-1]\n",
    "        n = len(s)\n",
    "        dp = [[0 for j in range(n + 1)] for i in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        return n - dp[-1][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = i+l-1\n",
    "                if j >= n: break\n",
    "                if l == 2:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "                # if s[i] == s[j]:\n",
    "                #     if l == 2:\n",
    "                #         dp[i][j] = 0\n",
    "                #     else:\n",
    "                #         dp[i][j] = dp[i+1][j-1]\n",
    "                # else:\n",
    "                #     if l == 2:\n",
    "                #         dp[i][j] = 1\n",
    "                #     else:\n",
    "                #         dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "        print(dp)\n",
    "        return dp[0][-1] <= k\n",
    "\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def isValid(left, right, k):\n",
    "        #     while left < right:\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #             right -= 1\n",
    "        #         else:\n",
    "        #             if k > 0:\n",
    "        #                 k -= 1\n",
    "        #                 return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "        #             else:\n",
    "        #                 return False\n",
    "        #     return True \n",
    "        # return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [[-1 for _end in range(len(s))] for _start in range(len(s))]\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        n = len(s)\n",
    "        def dfs(i, j): # longest palindrome subsequence\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if i > j:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if s[i] == s[j]:\n",
    "                res = max(res, dfs(i+1, j-1) + 2)\n",
    "            else:\n",
    "                res = max(res, dfs(i+1, j), dfs(i, j-1))\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        return dfs(0, n-1) >= n -k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i >j :\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i +1, j -1) + 2\n",
    "            else:\n",
    "                res = max(dfs(i +1, j), dfs(i, j-1))\n",
    "            memo[(i, j)] = res\n",
    "            return memo[(i, j)]\n",
    "        return len(s) - dfs(0, len(s) -1) <= k\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i +1, j -1) + 2\n",
    "            else:\n",
    "                x = dfs(i +1, j)\n",
    "                y = dfs(i, j -1)\n",
    "                # res = max(res, x, y) # wrong: reference before assign \n",
    "                res = max(x, y)\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        n = len(s)\n",
    "        res = dfs(0, n -1)\n",
    "        return n - res <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        a = s\n",
    "        n = len(a)\n",
    "        @cache \n",
    "        def f(i, j):\n",
    "            if i==j:\n",
    "                return 1 \n",
    "            else:\n",
    "                if j<i:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    if a[i]==a[j]:\n",
    "                        return 2 + f(i+1, j-1)\n",
    "                    else:\n",
    "                        return max(f(i+1, j), f(i, j-1))\n",
    "        b = f(0, n-1)\n",
    "        if k>=(n-b):\n",
    "            return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     # 区间i,j 能否在k宽容度下成为palindrome\n",
    "        #     if j-i+1 <= k:\n",
    "        #         return True\n",
    "        #     elif k == -1:\n",
    "        #         return False\n",
    "            \n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1,k)\n",
    "            \n",
    "        #     return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        # return dfs(0,n-1,k)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # to make ij palindrome, minimal k\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j), dfs(i,j-1))+1\n",
    "        return dfs(0,n-1) <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i + 1, j - 1) + 2\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        return len(s) - dfs(0, n - 1) <= k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(l, r, c):\n",
    "            n = r - l + 1\n",
    "            if n == 1 or n == 2 and s[l] == s[r]: # 最后一段(最中间)\n",
    "                return True\n",
    "            if s[l] == s[r]:\n",
    "                return dfs(l+1, r-1, c)\n",
    "            elif c == 0: # 退格键已用完\n",
    "                return False\n",
    "            return dfs(l, r-1, c-1) or dfs(l+1, r, c-1)\n",
    "\n",
    "        return dfs(0, len(s)-1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def isValid(left, right, k):\n",
    "            while left < right:\n",
    "                if s[left] == s[right]:\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if k > 0:\n",
    "                        k -= 1\n",
    "                        return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "                    else:\n",
    "                        return False\n",
    "            return True \n",
    "        return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i,j,k):\n",
    "            # 区间i,j 能否在k宽容度下成为palindrome\n",
    "            if j-i+1 <= k:\n",
    "                return True\n",
    "            elif k == -1:\n",
    "                return False\n",
    "            \n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1,k)\n",
    "            \n",
    "            return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        return dfs(0,n-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(x, c):\n",
    "            n = len(x)\n",
    "            if n == 1 or n == 2 and x[0] == x[1]: # 最后一段(最中间)\n",
    "                return True\n",
    "            if x[0] == x[-1]:\n",
    "                return dfs(x[1:-1], c)\n",
    "            elif c == 0: # 退格键已用完\n",
    "                return False\n",
    "            return dfs(x[0:-1], c-1) or dfs(x[1:], c-1)\n",
    "            \n",
    "        return dfs(s, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ss, kk):\n",
    "            if len(ss)==1 or (len(ss)==2 and ss[0]==ss[1]):\n",
    "                return True\n",
    "            if kk<=0 and ss[0]!=ss[-1]:\n",
    "                return False\n",
    "            if ss[0]==ss[-1]:\n",
    "                return dfs(ss[1:-1], kk)\n",
    "            else:\n",
    "                return dfs(ss[:-1], kk-1) or dfs(ss[1:], kk-1)\n",
    "\n",
    "\n",
    "        return dfs(s, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        left =  ['(', '{', '[']\n",
    "        right = [')', '}', ']']\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c in left:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if not stack:\n",
    "                    return False\n",
    "                else:\n",
    "                    if left.index(stack[-1]) != right.index(c):\n",
    "                        return False\n",
    "                    else:\n",
    "                        stack = stack[:-1]\n",
    "        return len(stack) == 0\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: 'str') -> 'bool':\n",
    "        _dic = {\")\":\"(\",\n",
    "               \"]\":\"[\",\n",
    "               \"}\":\"{\"}\n",
    "        # if s[0] in _dic:\n",
    "        #     return False\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i not in _dic:\n",
    "                stack.append(i)\n",
    "            elif not stack or _dic[i]!=stack.pop():\n",
    "                return False\n",
    "        return not stack\n",
    "    \n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # dict_s = {\n",
    "        #     '(':0,\n",
    "        #     '[':1,\n",
    "        #     '{':2,\n",
    "        #     ')':3,\n",
    "        #     ']':4,\n",
    "        #     '}':5\n",
    "        # }\n",
    "        # s = list(map(lambda x:dict_s[x],s))\n",
    "        # q = [10]\n",
    "        # temp = s[:]\n",
    "        # for i in s:\n",
    "        #     t = temp.pop()\n",
    "        #     print(t)\n",
    "        #     if (q[-1] - t)==3:\n",
    "        #         q.pop()\n",
    "        #     else:\n",
    "        #         q.append(t)\n",
    "        # if q==[10]:\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "        \n",
    "        # q = ['#']\n",
    "        # temp = list(s)[:]\n",
    "        # for i in s:\n",
    "        #     t = temp.pop()\n",
    "        #     if (t=='(' and q[-1]==')') or (t=='[' and q[-1]==']') or (t=='{' and q[-1]=='}'):\n",
    "        #         q.pop()\n",
    "        #     else:\n",
    "        #         q.append(t)\n",
    "        # if q==['#']:\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "        \n",
    "        q = ['#']\n",
    "        temp = list(s)[:]\n",
    "        for i in s:\n",
    "            t = temp.pop()\n",
    "            if (t=='(' and q[-1]==')') or (t=='[' and q[-1]==']') or (t=='{' and q[-1]=='}'):\n",
    "                q.pop()\n",
    "            else:\n",
    "                q.append(t)\n",
    "        return q==['#']\n",
    "        \n",
    "#         tosee = []\n",
    "        \n",
    "#         for c in s:\n",
    "#             if c == \"(\":\n",
    "#                 tosee.append(\")\")\n",
    "#             elif c == \"{\":\n",
    "#                 tosee.append(\"}\")\n",
    "#             elif c == \"[\":\n",
    "#                 tosee.append(\"]\")\n",
    "#             elif tosee:\n",
    "#                 if c != tosee.pop(): return False\n",
    "#             else:\n",
    "#                 return False\n",
    "            \n",
    "#         return not tosee\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        info = {\n",
    "            \")\": \"(\",\n",
    "            \"]\": \"[\",\n",
    "            \"}\": \"{\"\n",
    "        }\n",
    "        open = [\"(\", \"[\", \"{\"]\n",
    "        close = [\")\", \"]\", \"}\"]\n",
    "        try:\n",
    "            eval(s)\n",
    "            return True\n",
    "        except:\n",
    "            res = []\n",
    "            for i in s:\n",
    "                if i in open:\n",
    "                    res.append(i)\n",
    "                else:\n",
    "                    try:\n",
    "                        assert info[i] == res[-1]\n",
    "                        res.pop()\n",
    "                    except:\n",
    "                        return False\n",
    "            return False if len(res) else True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        left = ['(','[','{']\n",
    "        right = {')':'(',']':'[','}':'{'}\n",
    "        sleft=[]\n",
    "        for i in s: \n",
    "            if i in left:\n",
    "                sleft.append(i)\n",
    "            else:\n",
    "                if sleft == []:\n",
    "                    return False\n",
    "                \n",
    "                if right[i] != sleft.pop():\n",
    "                    return False\n",
    "        if sleft != []:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: 'str') -> 'bool':\n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        chs = {')':'(', ']':'[', '}':'{'}\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c in chs:\n",
    "                if len(stack) == 0:\n",
    "                    return False\n",
    "                if stack.pop() != chs[c]:\n",
    "                    return False\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return len(stack) == 0\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        s = list(s)\n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        elif len(s)%2 == 1:\n",
    "            return False\n",
    "        stack = []\n",
    "        mapping = {\")\":\"(\",\"]\":\"[\",\"}\":\"{\"}\n",
    "        for ix in range(len(s)):\n",
    "            if s[ix] in mapping.values():\n",
    "                stack.append(s[ix])\n",
    "            elif len(stack) == 0:\n",
    "                return False\n",
    "            elif mapping[s[ix]] == stack[-1]:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "        if len(stack) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        \n",
    "        mapping = {\")\":\"(\",\"}\":\"{\",\"]\":\"[\"}\n",
    "        \n",
    "        for char in s:\n",
    "            if char in mapping:\n",
    "                top_element = stack.pop() if stack else '#'\n",
    "                \n",
    "                if mapping[char]!=top_element:\n",
    "                    return False\n",
    "            else:\n",
    "                stack.append(char)\n",
    "                \n",
    "        return not stack\n",
    "            \n",
    "                 \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dict_s = {\n",
    "            '(':0,\n",
    "            '[':1,\n",
    "            '{':2,\n",
    "            ')':3,\n",
    "            ']':4,\n",
    "            '}':5\n",
    "        }\n",
    "        s = list(map(lambda x:dict_s[x],s))\n",
    "        q = [10]\n",
    "        temp = s[:]\n",
    "        for i in s:\n",
    "            t = temp.pop()\n",
    "            print(t)\n",
    "            if (q[-1] - t)==3:\n",
    "                q.pop()\n",
    "            else:\n",
    "                q.append(t)\n",
    "        if q==[10]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if s is None:\n",
    "            return False\n",
    "        left=['(', '[', '{']\n",
    "        right=[')', ']', '}']\n",
    "        full=['()', '[]', '{}']\n",
    "        \n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i in left:\n",
    "                stack.append(i)\n",
    "            elif i in right:\n",
    "                if stack == []:\n",
    "                    return False\n",
    "                else:\n",
    "                    test = stack.pop(-1) + i\n",
    "                    if test not in full:\n",
    "                        return False\n",
    "        if len(stack):\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "                    \n",
    "                \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        if len(s) % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in list(s):\n",
    "            print(c)\n",
    "            if c == '(' or c == '[' or c == '{' :\n",
    "                stack.append(c)\n",
    "                continue\n",
    "            if c == ')':\n",
    "                if len(stack) == 0 or stack[len(stack) - 1] != '(':\n",
    "                    return False\n",
    "            if c == ']':\n",
    "                if len(stack) == 0 or stack[len(stack) - 1] != '[':\n",
    "                    return False\n",
    "            if c == '}':\n",
    "                if len(stack) == 0 or stack[len(stack) - 1] != '{':\n",
    "                    return False\n",
    "            stack.pop()\n",
    "\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        dc = {\"{\": \"}\", \"[\": \"]\", \"(\": \")\"}\n",
    "        stack = []\n",
    "        for st in s:\n",
    "            if len(stack) > 0 and dc.get(stack[len(stack)-1]) == st:\n",
    "                    stack.pop()\n",
    "            else:\n",
    "                stack.append(st)\n",
    "        return stack == []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        t=[None]\n",
    "        for a in s:\n",
    "            if a in '[{(':\n",
    "                t.append(a)\n",
    "            else:\n",
    "                b=a\n",
    "                a=t[-1]\n",
    "                #print(b,a)\n",
    "                \n",
    "                if a is None or a not in '[{(':\n",
    "                    return False\n",
    "                if a=='(' and b!=')':\n",
    "                    return False\n",
    "                if a=='[' and b!=']':\n",
    "                    return False\n",
    "                if a=='{' and b!='}':\n",
    "                    return False\n",
    "                t.pop()\n",
    "          #  print(t)\n",
    "        return len(t)==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        a = []\n",
    "        for i in s:\n",
    "            if i == \"(\" or i == \"[\" or i == \"{\":\n",
    "                a.append(i)\n",
    "            elif i == \")\":\n",
    "                if len(a) == 0:\n",
    "                    return False\n",
    "                elif a[-1] != \"(\":\n",
    "                    return False\n",
    "                else:\n",
    "                    a.pop()\n",
    "            elif i == \"]\":\n",
    "                if len(a) == 0:\n",
    "                    return False\n",
    "                elif a[-1] != \"[\":\n",
    "                    return False\n",
    "                else:\n",
    "                    a.pop()\n",
    "            elif i == \"}\":\n",
    "                if len(a) == 0:\n",
    "                    return False\n",
    "                elif a[-1] != \"{\":\n",
    "                    return False\n",
    "                else:\n",
    "                    a.pop()\n",
    "        if(a.__len__() == 0):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        dic = {')':'(' ,']':'[' ,'}':'{'}\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if stack and i in dic.keys():\n",
    "                #出栈（相应的内容）\n",
    "                ls = stack.pop()\n",
    "                if ls == dic[i]:\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                #入栈\n",
    "                stack.append(i)\n",
    "        return not len(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 2:\n",
    "            return False\n",
    "        while '()' in s or '[]' in s or '{}' in s:\n",
    "            s = s.replace('()', '').replace('[]', '').replace('{}', '')\n",
    "        return s == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def isValid(self, s: str) -> bool:\n",
    "        # if len(s) % 2 !=0:\n",
    "        #     return False\n",
    "        # n = len(s)\n",
    "        # cur = 0\n",
    "        # dic = {'[':']','(':')','{':'}'}\n",
    "        # if s[0] in dic.values():\n",
    "        #     return False\n",
    "        # for i in range(n):\n",
    "        #     if s[i] in dic.keys():\n",
    "        #         cur += 1\n",
    "        #         pass\n",
    "        #     elif s[i] in dic.values():\n",
    "        #         f = i\n",
    "        #         e=0\n",
    "        #         try:\n",
    "        #             while cur>=1:\n",
    "        #                 e +=1\n",
    "        #                 j = i-e\n",
    "        #                 if dic[s[j]] != s[f]:\n",
    "        #                     return False\n",
    "        #                 else:\n",
    "        #                     f += 1\n",
    "        #                     cur -= 1\n",
    "        #         except:\n",
    "        #             return False\n",
    "        # print(cur)\n",
    "        # if cur == 0:\n",
    "        #     return True  \n",
    "        # else:\n",
    "        #     return False\n",
    "    def isValid(self, s):\n",
    "            while '{}' in s or '()' in s or '[]' in s:\n",
    "                s = s.replace('{}', '')\n",
    "                s = s.replace('[]', '')\n",
    "                s = s.replace('()', '')\n",
    "            return s == ''\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        while '{}' in s or '()' in s or '[]' in s:\n",
    "            s = s.replace('{}', '')\n",
    "            s = s.replace('[]', '')\n",
    "            s = s.replace('()', '')\n",
    "        return s == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        balanced = True\n",
    "        index = 0\n",
    "        while index < len(s) and balanced:\n",
    "            symbol = s[index]\n",
    "            if symbol in \"([{\":\n",
    "                stack.append(symbol)\n",
    "            else:\n",
    "                if stack == []:\n",
    "                    balanced = False\n",
    "                else:\n",
    "                    top = stack.pop()\n",
    "                    if not self.matches(top, symbol):\n",
    "                        balanced = False\n",
    "            index += 1\n",
    "        if balanced and stack == []:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def matches(self,open,close):\n",
    "        opens=\"([{\"\n",
    "        closes = \")]}\"\n",
    "        return opens.index(open) == closes.index(close)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 2 != 0:\n",
    "            return False\n",
    "        else:\n",
    "            hashtable = {\"{\":\"}\",\"[\":\"]\",\"(\":\")\",\"?\":\"?\"}\n",
    "            stack = [\"?\"]\n",
    "            for i in list(s):\n",
    "                # 遍历每个字符串，如果是左括号，入栈，如果是右括号，判断出栈的左括号和右括号是否配对，配对就成功出栈，不配对则无效\n",
    "                if i in hashtable:\n",
    "                    stack.append(i)\n",
    "                elif hashtable[stack.pop()] != i:\n",
    "                    return False\n",
    "            if len(stack) == 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if s == \"\":\n",
    "            return True\n",
    "        stack = []\n",
    "        for each in s:\n",
    "            print(each)\n",
    "            if each == '(':\n",
    "                stack.append('(')\n",
    "                continue\n",
    "            if each == '{':\n",
    "                stack.append('{')\n",
    "                continue\n",
    "            if each == '[':\n",
    "                stack.append('[')\n",
    "                continue\n",
    "            if len(stack) == 0:\n",
    "                return False\n",
    "            if each == ')':\n",
    "                if stack.pop() == '(':\n",
    "                    continue\n",
    "                return False\n",
    "            if each == '}':\n",
    "                if stack.pop() == '{':\n",
    "                    continue\n",
    "                return False\n",
    "            if each == ']':\n",
    "                if stack.pop() == '[':\n",
    "                    continue\n",
    "                return False\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import logging\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        pair_dict = {')': '(', ']': '[', '}': '{'}\n",
    "\n",
    "        for c in s:\n",
    "            if c in pair_dict:\n",
    "                if not stack or stack[-1] != pair_dict[c]:\n",
    "                    return False\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def log(*args, **kwargs):\r\n",
    "    # if(kwargs != {}):\r\n",
    "    #     print(\"log\", *args, kwargs)\r\n",
    "    # else:\r\n",
    "    #     print(\"log\", *args)\r\n",
    "    pass\r\n",
    "class Solution:\r\n",
    "    def isValid(self, s: str) -> bool:\r\n",
    "        stack = []\r\n",
    "        for i in range(len(s)):\r\n",
    "            c = s[i]\r\n",
    "            if \"([{\".find(c) != -1:\r\n",
    "                stack.append(c)\r\n",
    "            if \")]}\".find(c) != -1:\r\n",
    "                if len(stack) <= 0:\r\n",
    "                    log(\"stack len 0\", c)\r\n",
    "                    return False\r\n",
    "                if self.check(c, stack[-1]):\r\n",
    "                    stack.pop(-1)\r\n",
    "                    log(\"check pass\", stack)\r\n",
    "                else:\r\n",
    "                    return False\r\n",
    "            log(f\"c = {c} stack = {stack}\")\r\n",
    "\r\n",
    "        if len(stack) > 0:\r\n",
    "            log(\"stack len too long\", stack)\r\n",
    "            return False\r\n",
    "        \r\n",
    "        return True\r\n",
    "\r\n",
    "    def check(self, c, top):\r\n",
    "        if top == \"(\" and c == \")\":\r\n",
    "            return True\r\n",
    "        if top == \"[\" and c == \"]\":\r\n",
    "            return True\r\n",
    "        if top == \"{\" and c == \"}\":\r\n",
    "            return True\r\n",
    "        return False\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        if (length%2) != 0:\n",
    "            return False\n",
    "        s_dic = {\")\":\"(\",\"]\":\"[\",\"}\":\"{\"}\n",
    "        s_list = []\n",
    "        for i in s:\n",
    "            if i in s_dic:\n",
    "                if not s_list or s_list[-1] != s_dic[i]:\n",
    "                    return False\n",
    "                s_list.pop()\n",
    "            else:\n",
    "                s_list.append(i)\n",
    "        return not s_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        opens = '([{'\n",
    "        closers = ')]}'\n",
    "        tmp = []\n",
    "        for c in s:\n",
    "            if c in opens:\n",
    "                tmp.append(c)\n",
    "            else:\n",
    "                if not tmp or opens[closers.index(c)] != tmp.pop():\n",
    "                    return False\n",
    "        return not tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while '()' in s or '[]' in s or '{}' in s:\n",
    "            s = s.replace('()', '')\n",
    "            s = s.replace('[]', '')\n",
    "            s = s.replace('{}', '')\n",
    "        if s=='':\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s)<2:\n",
    "            return False\n",
    "        stack = []\n",
    "        dic = {\n",
    "            ')':'(',\n",
    "            '}':'{',\n",
    "            ']':'['\n",
    "        }\n",
    "        for i in range(len(s)):\n",
    "            x = s[i]\n",
    "            if x in dic:\n",
    "                if len(stack) != 0:\n",
    "\n",
    "                    if dic[x] == stack[-1]:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                stack.append(x)\n",
    "        \n",
    "        return len(stack) == 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if len(s) % 2 == 1:\n",
    "        #     return False\n",
    "        # pairs = {\n",
    "        #     \")\":\"(\",\n",
    "        #     \"]\":\"[\",\n",
    "        #     \"}\":\"{\"\n",
    "        # }\n",
    "        # n = len(s)\n",
    "        # stack = []\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] in pairs:\n",
    "        #         if not stack or stack[-1] != pairs[s[i]]:\n",
    "        #             return False\n",
    "                \n",
    "        #         stack.pop()\n",
    "        #     else:\n",
    "        #         stack.append(s[i])\n",
    "        # return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        l = len(s)\n",
    "        sta = [0 for _ in range(0, l + 1)]\n",
    "        top = -1\n",
    "        dic = {'(': 1, ')': -1, '[': 2, ']': -2, '{': 3, '}': -3}\n",
    "        for i in range(0 , l):\n",
    "            x = dic[s[i]]\n",
    "            if x > 0:\n",
    "                top += 1\n",
    "                sta[top] = x\n",
    "            else:\n",
    "                if top < 0:\n",
    "                    return False\n",
    "                y = sta[top]\n",
    "                if x + y == 0:\n",
    "                    top -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        if top >= 0:\n",
    "            return False\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self,val,next):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "class LStack:\n",
    "    def __init__(self):\n",
    "        self._top=None\n",
    "    def is_empty(self):\n",
    "        return self._top is None\n",
    "    def push(self,item):\n",
    "        self._top=ListNode(item,self._top)\n",
    "    def pop(self):\n",
    "        e=self._top.val\n",
    "        self._top=self._top.next\n",
    "        return e \n",
    "    def top(self):\n",
    "        return self._top.val\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        ls=LStack()\n",
    "        d={\")\":\"(\",\"]\":\"[\",\"}\":\"{\"}\n",
    "        for c in s:\n",
    "            if c in \"([{\":\n",
    "                ls.push(c)\n",
    "            else:\n",
    "                if (not ls.is_empty()) and ls.top() == d[c]:\n",
    "                    ls.pop()\n",
    "                else:\n",
    "                    return False\n",
    "        if ls.is_empty():\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "            l=len(s)\n",
    "            for i in range(int(l/2)):\n",
    "                s=s.replace('[]','')\n",
    "                s=s.replace('()','')\n",
    "                s=s.replace('{}', '')\n",
    "            if s=='':\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i=='(' or i=='{' or i=='[':\n",
    "                stack.append(i)\n",
    "            elif i==')':\n",
    "                j = stack.pop() if stack else None\n",
    "                if not j=='(': return False\n",
    "            elif i=='}':\n",
    "                j = stack.pop() if stack else None\n",
    "                if not j=='{': return False\n",
    "            elif i==']':\n",
    "                j = stack.pop() if stack else None\n",
    "                if not j=='[': return False\n",
    "        if len(stack)!=0: return False\n",
    "        else: return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 2 == 1:\n",
    "            return False\n",
    "        pairs = {\n",
    "            \")\":\"(\",\n",
    "            \"]\":\"[\",\n",
    "            \"}\":\"{\",\n",
    "        }\n",
    "        stack = list()\n",
    "        for ch in s:\n",
    "            if ch in pairs:\n",
    "                if not stack or stack[-1] != pairs[ch]:\n",
    "                    return False\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "        return not stack"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
